#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

typedef struct polynode
{
	double c;			        
	int e;				        
	struct polynode *next;		      
}PNode,*Polyn;                                  
Polyn h1, h2;				
double a[20];					
int b[20];				        
void Read(char *s)		 
{
	double c;
	int i = 0, e;
	ifstream infile(s)
	if (!infile)				
	{
        cout << "file open error!" << endl;
		exit(0);
	}
	while (1)                            
	{
		infile >> c >> e;
		if (infile.eof())
			break;
		a[i] = c;
		b[i] = e;
		i++;
	}
	infile.close();			
}
void Write(Polyn h)			
{
	ofstream outfile("multiply.txt");      
	Polyn p = h->next;                      
	if (!outfile)				
	{
		cout << "file open error!" << endl;
		exit(0);
	}
	if (!p)			                
		outfile << "0" << endl;
	while (p)			        
	{
		outfile << p->c << "     " << p->e << endl;
		p = p->next;
	}
	outfile.close();
}
 
void clearArray() {             
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
}
 
Polyn Create(char *s)			       
{
	int i = 0;                             
	Polyn h, last, p;
	h = new PNode;
	h->next = NULL;                        
	last = h;
    clearArray();
	Read(s);                               
	while (a[i]!=0)
	{
		p = new PNode;
		p->c = a[i];
		p->e = b[i];
		p->next = NULL;		      
		last->next = p;
		last = p;                     
		i++;
	}
	return h;
}
 
void PrintPoly(Polyn h)                       
{
	Polyn p = h->next;
	if (!p)                             
		cout << "0" << endl;
	while (p)
	{
		if (p->next)                     
		{
			if (p->next->c < 0)        
			{
				if (p->c == -1)     
				{
					cout << "-x^" << p->e;
					p = p->next;
				}
				else if (p->c == 1) 
				{
					cout << "x^" << p->e;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e;
					p = p->next;
				}
			}
			else if (p->next->c > 0)      
			{
				if (p->c == 1)         
				{
					cout << "x^" << p->e << "+";
					p = p->next;
				}
				else if (p->c == -1)   
				{
					cout << "-x^" << p->e << "+";
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << "+";
					p = p->next;
				}
			}
		}
		else                               
		{
			if (p->c < 0)              
			{
				if (p->c == -1)
				{
					cout << "-x^" << p->e << endl;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << endl;
					p = p->next;
				}
			}
			else if (p->c > 0)         
			{
				if (p->c == 1)
				{
					cout << "x^" << p->e << endl;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << endl;
					p = p->next;
				}	
			}	
		}
	}
}
void CreateNode(Polyn &p)			
{
	p = new PNode;
}
void DeleteNode(Polyn &p)			
{
	delete p;
}
Polyn add(Polyn h1, Polyn h2)                   
{
	Polyn p1, p2, p3, h, p;			
	p1 = h1->next;
	p2 = h2->next;
	CreateNode(h);
	p3 = h;
	while (p1&&p2)
	{
		if (p1->e < p2->e)              
		{
			p = p1;
			p1 = p1->next;
		}
		else if (p2->e < p1->e)         
		{
			p = p2;
			p2 = p2->next;
		}
		else                             
		{
			p1->c += p2->c;         
			if (p1->c == 0)         
			{
				p = p1;
				p1 = p1->next;
				DeleteNode(p);        
				p = p2;
				p2 = p2->next;
				DeleteNode(p);
				continue;
			}
			p = p2;                 
			p2 = p2->next;
			DeleteNode(p);
			p = p1;                 
			p1 = p1->next;
		}
		p3->next = p;                
		p3 = p;
	}
	if (p1)
		p3->next = p1;
	else if (p2) 
        p3->next = p2;                      
	else
		p3->next = NULL;
	h1->next = h2->next = NULL;        
	return h;
}
Polyn mul(Polyn hp, Polyn hq)		    
{
	Polyn hr, ht, q, p, pt;
	CreateNode(hr);
	hr->next = NULL;                     
	CreateNode(ht);
	ht->next = NULL;                     
	q = hq->next;
	while (q)
	{
		pt = ht;
		p = hp->next;
		while (p)
		{
			CreateNode(pt->next);	
			pt = pt->next;
			pt->c = p->c*q->c;      
			pt->e = p->e + q->e;    
			p = p->next;
		}
		pt->next = NULL;
		q = q->next;
		p = add(hr, ht);                 
		DeleteNode(hr);
		hr = p;
	}
	DeleteNode(ht);
	return hr;
}
int main()
{
	Polyn h1, h2, h3;                     
	cout << "读取文件，直到读入0时停止，建立单向链表" << endl;
	h1 = Create("polynode1.txt");
	h2 = Create("polynode2.txt");
	cout << "P(x) = ";
	PrintPoly(h1);
	cout << "Q(x) = ";
	PrintPoly(h2);
	h3 = mul(h1, h2);
	cout << "R(x) = P(x) * Q(x) = ";
	PrintPoly(h3);
	Write(h3);                             
	return 0;
}